public class MyLIst {
    public class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }

        //BM1 反转链表
        public class Solution {
            public ListNode ReverseList(ListNode head) {
                // write code here
                if (head == null || head.next == null) {
                    return head;
                }
                ListNode cur = head;
                ListNode curn = cur.next;
                head.next = null;
                while (curn != null) {
                    ListNode curnn = curn.next;
                    curn.next = cur;
                    cur = curn;
                    curn = curnn;
                }
                return cur;
            }
        }

        //BM2 在链表内指定区间反转
        public class Solution2 {
            public ListNode reverseBetween(ListNode head, int m, int n) {
                // write code here
                if (head == null || head.next == null || m >= n) {
                    return head;
                }
                ListNode cur = head;
                int num = 1;
                ListNode curmm = cur;
                while (num != m) {
                    if (cur.next == null) {
                        return head;
                    }
                    if (num == m - 1) {
                        curmm = cur;
                    }
                    cur = cur.next;
                    num++;
                }
                ListNode curm = cur;
                ListNode curn = cur.next;
                while (num != n) {
                    if (curn == null) {
                        break;
                    }
                    ListNode curnn = curn.next;
                    curn.next = cur;
                    cur = curn;
                    curn = curnn;
                    num++;
                }
                ListNode curN = cur;
                if (m == 1) {
                    head = curN;
                } else {
                    curmm.next = curN;
                }
                if (curn != null) {
                    curm.next = curn;
                } else {
                    curm.next = null;
                }
                return head;
            }
        }

        //BM4 合并两个排序的链表
        public class Solution3 {
            public ListNode Merge(ListNode pHead1, ListNode pHead2) {
                // write code here
                if (pHead1 == null) {
                    return pHead2;
                }
                if (pHead2 == null) {
                    return pHead1;
                }
                ListNode head = pHead1;
                ListNode cur1 = pHead1;
                ListNode cur2 = pHead2;
                if (cur1.val < cur2.val) {
                    head = cur1;
                    cur1 = cur1.next;
                } else {
                    head = cur2;
                    cur2 = cur2.next;
                }
                ListNode cur = head;
                while (cur1 != null && cur2 != null) {
                    if (cur1.val < cur2.val) {
                        cur.next = cur1;
                        cur = cur.next;
                        cur1 = cur1.next;
                    } else {
                        cur.next = cur2;
                        cur = cur.next;
                        cur2 = cur2.next;
                    }
                }
                if (cur1 == null) {
                    cur.next = cur2;
                } else if (cur2 == null) {
                    cur.next = cur1;
                }
                return head;
            }
        }

        //BM5 合并k个已排序的链表
        public class Solution4 {
            public ListNode mergeKLists(ArrayList<ListNode> lists) {
                // write code here
                int len = lists.size();
                if (len == 0) {
                    return null;
                }
                if (len == 1) {
                    return lists.get(0);
                }
                ListNode cur = lists.get(0);
                for (int i = 1; i < len; i++) {
                    cur = Merge(cur, lists.get(i));
                }
                return cur;
            }

            public ListNode Merge(ListNode pHead1, ListNode pHead2) {
                // write code here
                if (pHead1 == null) {
                    return pHead2;
                }
                if (pHead2 == null) {
                    return pHead1;
                }
                ListNode head = pHead1;
                ListNode cur1 = pHead1;
                ListNode cur2 = pHead2;
                if (cur1.val < cur2.val) {
                    head = cur1;
                    cur1 = cur1.next;
                } else {
                    head = cur2;
                    cur2 = cur2.next;
                }
                ListNode cur = head;
                while (cur1 != null && cur2 != null) {
                    if (cur1.val < cur2.val) {
                        cur.next = cur1;
                        cur = cur.next;
                        cur1 = cur1.next;
                    } else {
                        cur.next = cur2;
                        cur = cur.next;
                        cur2 = cur2.next;
                    }
                }
                if (cur1 == null) {
                    cur.next = cur2;
                } else if (cur2 == null) {
                    cur.next = cur1;
                }
                return head;
            }
        }

        //BM6 判断链表中是否有环
        public class Solution6 {
            public boolean hasCycle(ListNode head) {
                if (head == null || head.next == null) {
                    return false;
                }
                ListNode slow = head;
                ListNode fast = head;
                while (fast != null && fast.next != null) {
                    slow = slow.next;
                    fast = fast.next.next;
                    if (fast == slow) {
                        return true;
                    }
                }
                return false;
            }
        }
    }
}
